package 快速排序;

import java.util.Arrays;
//快排优化

public class quicksort1 {
    public static void swap(int[] array,int i,int j) {
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public static void quickSort1(int[] array) {
        quick1(array,0,array.length-1);
    }
    public static void quick1(int[] array,int left,int right) {
        if(left>=right) {
            return;
        }
        //找基准之前，找到中间大小的值(三数取中法)
        int midvalIndex=findMidValIndex(array,left,right);
        swap(array, midvalIndex,left);
        int pivot=partition1(array,left,right);//基准
        quick1(array,left,pivot-1);//递归基准的左边
        quick1(array,pivot+1,right);//递归基准的右边
    }
    public static int findMidValIndex(int[] array,int start,int end) {
        int mid=start+((end-start)>>>1);
        if(array[start]<array[end]) {
            if(array[mid]<array[start]) {
                return start;
            }else if(array[mid]>array[end]){
                return end;
            }else {
                return mid;
            }

        }else {
            if(array[mid]>array[start]) {
                return start;
            }else if(array[mid]<array[end]) {
                return end;
            }else {
                return mid;
            }
        }

    }
    public static  int partition1(int[] array,int start,int end) {
        //挖坑法
        int tmp=array[start];
        while(start<end) {
            while(start<end && array[end]>=tmp) {
                end--;
            }
            //end下标遇到了 小于 tmp的值
            array[start]=array[end];
            while(start<end && array[start]<=tmp) {
                start++;
            }
            //start 下标遇到了 大于tmp 的值
            array[end]=array[start];
        }
        array[start]=tmp;
        return start;
    }

    public static void main(String[] args) {
        int[] array={12,5,9,34,0,33,6,55};
        quickSort1(array);
        System.out.println(Arrays.toString(array));
    }
}
